package com.sfx.hot100;

import java.util.Random;

class Skiplist {

    public Skiplist() {

    }

    // 节点的最大层数
    private final int MAX_LEVEL = 10;

    static class Node {
        private int val;
        // 节点数组
        private Node[] next;

        public Node(int val) {
            this.val = val;
        }

        public Node() {

        }
    }

    // 当前跳表的头结点
    private final Node head = new Node();
    private Random random = new Random();

    // 我们这里要记录一下搜索的路径
    public Node[] find(int val) {
        Node[] path = new Node[MAX_LEVEL];
        //从头结点开始查询
        Node cur = head;
        for (int level = MAX_LEVEL - 1; level >= 0; level--) {
            // 如果 < val 继续向右走,否则向下走
            while (cur.next[level] != null && cur.next[level].val < val) {
                // 向右走
                cur = cur.next[level];
            }
            path[level] = cur;
        }
        return path;
    }

    private int randomLevel(int max) {
        int x = 1;
        while (x < max) {
            if (random.nextBoolean()) {
                return x;
            }
            x++;
        }
        return x;
    }

    public boolean search(int target) {
        Node[] path = find(target);
        return path[0].next[0] != null && path[0].next[0].val == target;
    }

    public void add(int num) {
        // 1. 确定要插入的位置
        Node[] path = find(num);
        // 2. 随机层数
        int level = randomLevel(MAX_LEVEL);
        // 3. 修改相邻节点的节点指针
        Node node = new Node(num);
        for (int i = 0; i < level; ++i) {
            node.next[i] = path[i].next[i];
            path[i].next[i] = node;
        }
    }

    public boolean erase(int num) {
        // 找到了再去删除
        Node[] path = find(num);
        Node node = path[0].next[0];
        // 没有找到
        if (node == null || node.val != num) {
            return false;
        }
        for (int i = 0; i < MAX_LEVEL; ++i) {
            if (path[i].next[i] != node) {
                break;
            }
            path[i].next[i] = node.next[i];
        }
        return true;
    }

    public static void main(String[] args) {

    }
}